#include <stdio.h>

#if 0
// 猴子吃桃：n个桃子 猴子每天吃剩下的桃子一半多一个 10天后 剩1个桃子 问第一天多少个桃子？
// 第10天  1个
// 第9天   4个
// 第8天   10个

// 递归：函数自己调用自己
    int MonkeyPeach(int day)
    {
        if(day == 10)   // 递归的终止条件（递归在写的时候一定要先定终止条件，不然容易陷入循环）
            return 1;
        return (MonkeyPeach(day + 1) + 1) * 2;  //递归体
    }
#endif

#if 0
// 求n的阶乘：n! = n * (n-1) * (n-2) * (n-3) ...... * 1
/* f(n) = n * f(n-1)
        = n * (n-1) * f(n-2)
        = ......
                    3 * f(2)
                        2 * f(1) 
*/

    int func(int n)
    {
        if(n == 1)
            return 1;
        return n * func(n - 1);
    }
#endif

#if 0
// 计算字符串长度
    int MyStrlen(char *s)
    {
        if(*s == '\0')
            return 0;
        return MyStrlen(s + 1) + 1;
    }
#endif

#if 1
// 青蛙 一次能跳1级台阶或2级台阶 问跳上n级台阶有几种跳法？（斐波那契数列）
    int JumpStep(int n)
    {
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        return JumpStep(n-1) + JumpStep(n-2);
    }
#endif

int main()
{
    // printf("%d\n", MonkeyPeach(8));
    // printf("%d\n", func(4));
    // char s[] = "hello world!";
    // printf("%d\n", MyStrlen(s));
    printf("%d\n", JumpStep(30)); // n大了会栈溢出

    return 0;
}